%!TEX program = xelatex
\documentclass[lang=cn,11pt,a4paper,citestyle =authoryear]{elegantpaper}

% 标题区域
\title{Mandelbrot Set的生成和探索}
\author{强基数学2001 \\ 关博仁}
\date{\zhtoday}

% 本文档命令
\usepackage{array,url,subfigure,stfloats}
\usepackage[lined,boxed,commentsnumbered]{algorithm2e}
\newcommand{\ccr}[1]{\makecell{{\color{#1}\rule{1cm}{1cm}}}}
\newcommand{\code}[1]{\lstinline{#1}}

% 文档区
\begin{document}

% 建立标题
\maketitle

% 摘要
\begin{abstract}
本文为浙江大学2021-2022短学期王何宇老师的《数学软件》课程作业，本文将详细介绍利用逃逸时间算法(The Escape Time Algorithm)在短时间内生成曼德勃罗集(Mandelbrot set)的方法，并且介绍所有相关代码实现和科学计算可视化工具使用，并伴随相关理论推导。本次作业将会发布到仓库\href{https://gitee.com/wellsguan/mathematics-software/tree/master/Day4}{Gitee/Day4}中。
\keywords{Mandelbrot集, Plotly, Python, 逃逸时间算法}
\end{abstract}

% 引言
\section{引言}

在本篇文章中我们将研究曼德勃罗集(Mandelbrot Set)，它是一个非常经典的动力系统理论与分形几何的例子。我们将主要从形如$z\mapsto z^2+c$的一族复映射中来探索这个兼具分析与几何性质的经典案例，若想从动力系统的角度更深层的了解其中的规律，可以参考[\cite{D.D.1984}]。此外本文将会从算法角度实现曼德勃罗集(Mandelbrot Set)的可视化并对算法效果进行具体分析，全部源代码可参见附录。

% 问题背景
\section{问题背景}

% 定义
\subsection{曼德勃罗集的定义}

曼德勃罗集(Mandelbrot Set,下文均以M-S指代)本质上是由下列式子定义的一个复数集:
\[
    \mathcal{M}=\{c|f(z)=z^2+c,\quad\lim\limits_{n\to\infty} f^n(0)<\infty\}
\]
形式较为简便，定义中涉及的迭代映射$f$有一系列较好的性质。

% 算法简介
\subsection{逃逸时间算法}

逃逸时间算法是一种研究分形几何的重要计算方法，其主要思想在于:
\begin{enumerate}
    \item 确定逃逸半径极限$r$并设置逃逸时间$N$(最大迭代次数)
    \item 对所选区域每一点进行迭代，并记录逃逸时间
    \item 根据逃逸时间生成可视化图形
\end{enumerate}
是一种高效的计算方法[\cite{张菊香2009}]。根据上述步骤可写出伪代码如下:

% 伪代码区
\begin{algorithm}
\caption{逃逸时间算法}\label{algorithm}
\KwIn{迭代函数$f$, 逃逸极限时间$N$, 逃逸半径极限$r$, 待检验集合$S$}
\KwOut{迭代次数映射$m$}
\KwData{}
\For{$x$ in $S$}{
    \For{$i$ in $1:N$}{
        $z = f(z)$\;
        \If{$|z|>r$}{$m(x)=i$\;对下一元素进行迭代\;}
    }
    $m(x)=N$
}
\end{algorithm}

% 数学理论
\section{逃逸半径极限的数学证明}

事实上，对于条件中给定的迭代，我们可以证明收敛的迭代数列中不存在模长大于2的项，即有如下定理:

\textbf{定理.}对于$f(z)=z^2+c$，$\lim\limits_{n\to\infty} f^n(0)<\infty$收敛等价于$\forall n\in\mathbb{N}, |f^n(z)|<=2$.
\textbf{证明.}\par
我们对$c$进行分类讨论，当$|c|<=2$:
\[|z_n|>2\implies |z_{n+1}|=|z_n^2+c|\geq|z_n^2|-|c|>2|z_n|-2>2\]
并且\[|z_{n+1}|-2>2(|z_n|-2)\]
这说明$|z_{n+1}-2|$发散，当$|c|\geq 2$:
\[|z_n| \geq |c| \implies |z_{n+1}| \geq |z_n|+(|c|-1)|z_n|+c \geq |z_n|+(|c|-2)|c|>|c| \]
这依然说明$|z_n|$发散，因此结论成立。

% 实验设计
\section{实验过程与实验结果}

\subsection{实验过程--代码实现}
本次实验使用\code{Python}语言并且伴随\code{Plotly}包进行科学计算可视化，\code{Python}的优点在于其内置的\code{numpy}包，对于大型矩阵生成计算十分方便，同时代码可读性强, 代码包中$main.py$文件如下，函数源代码参见附录:
\begin{lstlisting}
## 迭代次数
n = int(input())
## 矩形区域端点
z = -2.5-1.5j
w = 1+1.5j

## 输出矩阵区域内的Mandelbrot集
def mandelbrot():
    global z,w,n
    return mdb.generate_Mandelbrot_in_dec(z,w,n)
ans = mandelbrot()

## 显示Mandelbrot集
fig = px.imshow(ans[0], origin="lower", x=ans[1], y=ans[2]) #设置非矩阵显示模式, 并自定义坐标轴
fig.update_layout(
    title = dict(
        text = "Mandelbrot Set, N = "+str(n),
    )
)
fig.show()
\end{lstlisting}

支持用户自定义逃逸极限时间$N$与显示范围，初始设置可以完整显示画面，并且\code{Plotly}的可视化由Web实现，支持缩放功能，为此可以通过调整显示范围来更改观测精细度，初步有如下结果:
\begin{figure}[htbp]
    \centering
    \subfigure[N=10]{\includegraphics[width=0.28\textwidth]{../png/n_10_nonzoom.png}}
    \subfigure[N=100]{\includegraphics[width=0.28\textwidth]{../png/n_100_nonzoom.png}}
    \subfigure[N=1000]{\includegraphics[width=0.28\textwidth]{../png/n_1000_nonzoom.png}}
    \label{fig:my_label}
\end{figure}
\newline
从计算结果可见，迭代次数越多，边界越清晰，下面是调整至更小的矩形区域($z=-0.8+0.3i, w=-0.3+0.7i$)后的计算结果:
\begin{figure}[htbp]
    \centering
    \subfigure[N=10]{\includegraphics[width=0.28\textwidth]{../png/n_10_zoom.png}}
    \subfigure[N=100]{\includegraphics[width=0.28\textwidth]{../png/n_100_zoom.png}}
    \subfigure[N=1000]{\includegraphics[width=0.28\textwidth]{../png/n_1000_zoom.png}}
    \label{fig:my_label}
\end{figure}
\newpage
其中M-S的分形性质已经能够观察的较为清晰了，其部分星形分支在图中得以体现，但是相对之下，1000次的迭代计算时间已经相当长，为此没有尝试更高的数量级的迭代。\par

除此之外，对N=1000的放大图继续进行局部物理放大，有如下结果:
\begin{figure}[htbp]
    \centering
    \includegraphics[width = 0.8 \textwidth]{../png/n_1000_zoom2.png}
    \label{fig:my_label}
\end{figure}
结果较为精确且美妙。

% 结论区
\section{结论}
本次试验算法正确，计算精确度较高，生成图形较为美观，并且在一定程度上验证了M-S的图像是具有分形结构的。同时相比较之下，迭代次数多少对产生图形的精确度有显著影响，并且高迭代精度局部与迭代精度整体的形状相似，也从一定程度说明其迭代性质。

% 参考文献区
\nocite{*}
\printbibliography[heading=bibintoc, title=\ebibname]
\newpage

% 附录区
\appendix
\appendixpage
\addappheadtotoc

% 函数文件源代码
\section{mandelbrot.py}
\begin{lstlisting}
由于篇幅限制，源代码请参见此网址:https://gitee.com/wellsguan/mathematics-software/blob/master/Day4/src/mandelbrot.py
\end{lstlisting}

\end{document}
